A peer-to-peer architecture comprises a multitude of interconnected peers, some of which reside behind a network address translator (NAT) and/or a firewall. When a first peer desires to connect with a second peer that resides behind a NAT and/or a firewall, the first peer must somehow traverse through the NAT and/or firewall. Existing NAT traversal techniques leverage a server of the peer-to-peer architecture to perform the NAT traversal. However, these existing techniques contain several drawbacks. First, the existing techniques place a large overhead on the server of the peer-to-peer to architecture. Furthermore, because the peers rely upon the server, the existing techniques do not scale well in larger peer-to-peer architectures.